#include <stdio.h>

void merger(int *array, int left, int right) {
    if (right <= left) {
        return;
    }

    int middle = (left + right) / 2;

    merger(array, left, middle);
    merger(array, middle + 1, right);

    int i = left;
    int j = middle + 1;

    int k = 0;
    int temp[right - left + 1];
    while (i <= middle && j <= right) {
        if (array[i] < array[j]) {
            temp[k++] = array[i++];

        } else {
            temp[k++] = array[j++];
        }
    }

    while (i <= middle) {
        temp[k++] = array[i++];
    }

    while (j <= right) {
        temp[k++] = array[j++];
    }

    for (int i = left; i <= right; i++) {
        array[i] = temp[i - left];
    }
}

void mergerSort(int *array, int length) {
    merger(array, 0, length - 1);
}

